package com.fanco.learn_datastruct_leetcode.leetcode;


/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 *
 * @author admin
 */
public class Day04 {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1, 2, 9};
        int[] nums2 = {3, 4, 6};

        double mediaNum = solution.findMedianSortedArrays(nums1, nums2);
        System.out.println(mediaNum);

    }

    private static class Solution {

        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            // 1. 两个数组合并
            int[] mergeNums = mergeNums(nums1, nums2);
            printNums(mergeNums);
            // 2. 新数组排序
            int[] sortedNums = sortedNums(mergeNums);
            printNums(sortedNums);
            // 3. 取出中位数
            if (sortedNums.length % 2 == 0) {
                double num = (sortedNums[sortedNums.length / 2 - 1] + sortedNums[sortedNums.length / 2]) / 2.0;
                return num;
            } else {
                return sortedNums[sortedNums.length / 2];
            }
        }

        private int[] sortedNums(int[] mergeNums) {
            for (int i = 0; i < mergeNums.length - 1; i++) {
                for (int j = 0; j < mergeNums.length - 1 - i; j++) {
                    if (mergeNums[j + 1] < mergeNums[j]) {
                        int temp = mergeNums[j + 1];
                        mergeNums[j + 1] = mergeNums[j];
                        mergeNums[j] = temp;
                    }
                }
            }
            return mergeNums;
        }

        private int[] mergeNums(int[] nums1, int[] nums2) {
            int[] newNums = new int[nums1.length + nums2.length];
            for (int i = 0; i < nums1.length; i++) {
                newNums[i] = nums1[i];
            }
            for (int i = 0; i < nums2.length; i++) {
                newNums[nums1.length + i] = nums2[i];
            }
            return newNums;
        }

        private void printNums(int[] mergeNums) {
            for (int i = 0; i < mergeNums.length; i++) {
                System.out.print(mergeNums[i] + "\t");
            }
            System.out.println("\n");
        }
    }
}
